Java 集合框架 modCount 属性和 fast-fail 机制

2018-03-09

modCount 属性

在 AbstractCollection 中存在一个 modCount 属性：

/**
  * The number of times this list has been <i>structurally modified</i>.
  * 表示 List 结构被修改的次数。
  *
  * Structural modifications are those that change the size of the
  * list, or otherwise perturb it in such a fashion that iterations in
  * progress may yield incorrect results.
  * 结构被修改主要是指容量的变化，可能对迭代器迭代产生错误的结果
  *
  *
  * <p>This field is used by the iterator and list iterator implementation
  * returned by the {@code iterator} and {@code listIterator} methods.
  * 主要由 iterator 和 list 的 iterator 方法返回的迭代器使用
  * 
  * If the value of this field changes unexpectedly, the iterator (or list
  * iterator) will throw a {@code ConcurrentModificationException} in
  * response to the {@code next}, {@code remove}, {@code previous},
  * {@code set} or {@code add} operations.  
  * 如果此值发生改变，那么迭代器在进行 next, remove, previous, set, add 等操作时将抛
  * 出 ConcurrentModificationException 异常。
  * 
  * This provides
  * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
  * the face of concurrent modification during iteration.
  * 提供了 fail-fast 机制，防止在并发迭代时可能产生的不确定性问题。
  *
  * <p><b>Use of this field by subclasses is optional.</b> 
  * 字段是否使用此字段是可选的。
  * 
  * If a subclass wishes to provide fail-fast iterators (and list iterators), 
  * then it merely has to increment this field in its {@code add(int, E)} and
  * {@code remove(int)} methods (and any other methods that it overrides
  * that result in structural modifications to the list).  
  * 如果子类希望提供 fast-fail 机制，则需要在 add，remove, 或其他可修改集合结构的操作时
  * 对其自增
  * 
  * A single call to {@code add(int, E)} or {@code remove(int)} must add no 
  * more than one to this field, or the iterators (and list iterators) will 
  * throw bogus {@code ConcurrentModificationExceptions}.  

  * If an implementation does not wish to provide fail-fast iterators, this 
  * field may be ignored.
  * 如果实现类不想提供 fast-fail 机制，可以忽略此属性
  */
 protected transient int modCount = 0;

ConcurrentModificationException 和 fast-fail 机制

以 ArrayList 的迭代器为例：

public Iterator<E> iterator() {
    return new Itr();
}
    
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

迭代器进行实例化时，迭代器 expectedModeCount 属性初始值是被迭代的集合中的 modCount。
在迭代器调用 next 和 remove 方法时，会统一调用 checkForComdification 方法，该方法会每次检查 expectedModeCount 和当前被迭代的集合中的 modCount 值是否相等，不相等即抛出 ConcurrentModificationException 异常。

即迭代的时候，为了防止有其他线程在并发操作集合时，采用了该机制来防止多线程安全问题的产生。
利用 modCount 属性，在可以修改集合结构的方法内修改 modCount 值，并且在迭代的时候不断检查。
而这正是 fast-fail 机制。

解决 fast-fail

fast-fail 机制是防止多线程问题的一种手段，那么要解决该问题，只要遵循多线程并发问题的解决方法即可。

涉及到 modCount 方法上加 synchronized 关键字
使用 Collections.synchronizedList
使用并发包下的 CopyOnWriteArrayList 替换 ArrayList

CopyOnWriteArrayList 是首选，后续有机会会分析 CopyOnWriteArrayList 如何避免 fast-fail 机制的原理。